A technique has been known which arranges replicas, which are copies of data, in a plurality of nodes in storage systems including NoSQL, such as a distributed Key-Value Store (KVS). In the storage system to which the technique is applied, since the replicas are arranged in a plurality of nodes, data loss due to a disk failure is prevented. In addition, since data is allowed to be read from the replica arranged in each node, an access load is distributed.
In some case, the storage system requires strong consistency for guaranteeing the identity of data read from each replica. A chain replication technique has been known as an example of a method of maintaining the strong consistency. An example of the storage system to which the chain replication technique is applied will be described below.
First, an example of the process of the storage system when a client issues a Put request will be described with reference to FIG. 14. FIG. 14 is a first diagram illustrating an example of the chain replication. In the example illustrated in FIG. 14, a storage system to which Chain Replication with Apportioned Query (CRAQ) is applied as an example of the chain replication will be described.
In the example illustrated in FIG. 14, the storage system includes N nodes with the same replica. In the example illustrated in FIG. 14, nodes other than a first node, a second node, a third node, and an N-th node among the N nodes of the storage system are not illustrated.
When receiving the Put request issued by the client, each node of the storage system sequentially transmits an update request to write data along the path in which the nodes are sequentially arranged. For example, in the example represented by (A) in FIG. 14, the client issues the Put request to the first node. In this case, the first node prepares to write new data and transmits the update request to the second node as represented by (B) in FIG. 14.
Then, when receiving the update request from the first node, the second node prepares to write new data and transmits the update request to the third node. Then, each node sequentially transmits the update request to the N-th node, which is the last node of the path. As represented by (C) in FIG. 14, when receiving the update request, the N-th node, which is the last node of the path, writes new data and transmits an updated request, which is a response to the update request, to the previous node.
Then, when receiving the updated request, each node writes the prepared data and sequentially transmits the updated request to the first node, which is a start point, along the path. Then, as represented by (D) in FIG. 14, when receiving the updated request, the first node writes the prepared data and notifies the client that the writing process has ended.
Next, an example of the process performed by the storage system when the client issues a Get request will be described with reference to FIG. 15. FIG. 15 is a second diagram illustrating an example of the chain replication. In the example illustrated in FIG. 15, each of the first to N-th nodes transmits data for the stored replica in response to the Get request from each of the clients 17a to 17d. As such, the storage system distributes the destinations of the Get request, thereby improving the performance for the Get request.
In a case in which each node other than the N-th node prepares to write data, when the Get request is received from the client, the N-th node, which is the last node of the path, is inquired whether to write new data. When the N-th node writes new data, each node transmits data for the replica after the new data is written to the client. When the N-th node does not write new data, each node transmits data for the replica before new data is written to the client.
For example, when the Get request is acquired from the client for the time from the transmission of the update request to the reception of the updated request, the first node inquires the N-th node about whether to write new data, as represented by (E) in FIG. 15. When receiving a response indicating that the new data has been written from the N-th node, the first node outputs data after the new data is written to the client. When receiving a response indicating that the new data has not been written from the N-th node, the first node outputs data before the new data is written to the client.    Patent Document 1: Japanese Laid-open Patent Publication No. 2010-146067    Non-Patent Document 1: Object Storage on CRAQ, High-throughput chain replication for read-mostly workloads, Jeff Terrace and Michael J. Freedman Princeton University, USENIX annual Technical Conference. San Diego, Calif., June 2009    Non-Patent Document 2: Chain Replication for Supporting High Throughput and Availability, Robbert van Renesse, Fred B. Schneider, USENIX Association OSDI′ 04:6th Symposium on Operation Systems Design and Implementation
However, in the above-mentioned chain replication technique, it is difficult to change the number of nodes with the replica. Therefore, it is difficult to adjust the performance for the Put request and the performance for the Get request.
That is, when the number of nodes storing the replica increases, the performance for the Get request is also improved. However, when the number of nodes storing the replica increases, the number of destinations to which data is written increases, which results in the deterioration of the performance for the Put request. In addition, when the number of nodes storing the replica is reduced, the performance for the Put request is improved, but the number of replicas, which are the destinations of the Get request, is reduced. As a result, the performance for the Get request deteriorates.
Therefore, it is difficult for the storage system to set the number of nodes to an appropriate value when an improvement in the performance for the Put request is needed during the initialization of data for the replica and an improvement in the performance for the Get request is needed thereafter.